package blue_bridge_cup_learning.差分;

import java.util.*;

public class 一维差分模板 {
    public static void main(String[] args) {

        System.out.println("注意:差分数组的长度需要比原数组多1,否则在区间[l,r]中r取到最后一个位置时,diff_arr[r+1]会越界");
        int[] arr = { 0, 1, 2, 3, 4, 5, 6 };
        // 构建差分数组,长度比原数组多1
        int[] diff_arr = new int[arr.length + 1];
        // 构建差分数组,diff[i] = arr[i] - arr[i-1]
        for (int i = 1; i < arr.length; i++) {
            diff_arr[i] = arr[i] - arr[i - 1];
        }
        System.out.println("原数组：" + Arrays.toString(arr));
        System.out.println("差分数组：" + Arrays.toString(diff_arr));

        // 将区间[2,4]的每个数都加1
        add(diff_arr, 2, 4, 1);
        System.out.println("差分数组：" + Arrays.toString(diff_arr));

        // 通过差分数组还原出原数组(前缀和)
        int[] res = getSum(diff_arr);
        System.out.println("修改后的数组：" + Arrays.toString(res));
    }

    // 通过差分数组还原出原数组(前缀和)
    public static int[] getSum(int[] diff_arr) {
        int[] sum_arr = new int[diff_arr.length];
        for (int i = 1; i < diff_arr.length; i++) {
            sum_arr[i] = sum_arr[i - 1] + diff_arr[i];
        }
        return sum_arr;
    }

    // 将区间[l,r]内的每个数都加c
    public static void add(int[] diff_arr, int l, int r, int c) {
        diff_arr[l] += c;
        diff_arr[r + 1] -= c;
    }
}
